package hot100;

import java.util.ArrayList;
import java.util.List;

public class findAnagrams {
    public List<Integer> findAnagrams(String s, String p) {
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        // 将p对应的字母记录到hash1中
        for(int i = 0;i < p.length();i++) {
            hash1[p.charAt(i) - 'a']++;
        }
        int l = 0,r = 0;
        // tag 来标记 hash2 == hash1中存在值 的个数
        int tag = 0;
        List<Integer> ret = new ArrayList<>();

        while(r < s.length()) {
            //进窗口
            hash2[s.charAt(r) - 'a']++;
            if(hash2[s.charAt(r) - 'a'] <= hash1[s.charAt(r) - 'a']) {
                tag++;
            }
            //出窗口
            if(r - l + 1 > p.length()) {
                if(hash2[s.charAt(l) - 'a'] <= hash1[s.charAt(l) - 'a']) {
                    tag--;
                }
                hash2[s.charAt(l) - 'a']--;
                l++;
            }
            if(tag == p.length()) {
                ret.add(l);
            }
            r++;
        }
        return ret;
    }
}
